<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="My Personal Website For Blog">
  <meta name="author" content="黄宇辉">
  <meta name="keywords" content="learning note,hexo blog">
  <title>详解Linked list的实现方式及其应用 - 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/vs2015.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->
<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">

<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">

<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>ANONYMOUS</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                Home
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                Archives
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                Tags
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                About
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2019-04-19 11:54">
      April 19, 2019 am
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      3.4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      59
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
            <article class="markdown-body">
              <h2 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h2><h3 id="链表的定义"><a href="#链表的定义" class="headerlink" title="链表的定义"></a>链表的定义</h3><p><em><code>链表</code>是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列<code>结点</code>(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分: 一个是存储数据元素的<code>数据域</code>,另一个是存储下一个结点地址的<code>指针域</code>.</em></p>
<h3 id="链表的使用场景"><a href="#链表的使用场景" class="headerlink" title="链表的使用场景"></a>链表的使用场景</h3><ol>
<li>数据量较小.</li>
<li>不需要预先知道数据规模.</li>
<li>适应于频繁的插入操作.</li>
</ol>
<h3 id="链表的实现方式"><a href="#链表的实现方式" class="headerlink" title="链表的实现方式"></a>链表的实现方式</h3><h4 id="单向链表"><a href="#单向链表" class="headerlink" title="单向链表"></a>单向链表</h4><ol>
<li><em>首先定义一个链表</em><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.linkedlist;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: ListNode
 * <span class="hljs-doctag">@Description</span>: 单向链表
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 15, 2019 8:59:50 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SinglyListNode</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;

	<span class="hljs-keyword">private</span> E data;
	<span class="hljs-keyword">private</span> SinglyListNode&lt;E&gt; next;<span class="hljs-comment">// the pointer</span>

	<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">getData</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> data;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setData</span><span class="hljs-params">(E data)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.data = data;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> SinglyListNode&lt;E&gt; <span class="hljs-title">getNext</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> next;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setNext</span><span class="hljs-params">(SinglyListNode&lt;E&gt; next)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.next = next;
	&#125;
&#125;</code></pre></div></li>
<li><em>操作单向链表的示例程序</em><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.linkedlist;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: SinglyLinkedList
 * <span class="hljs-doctag">@Description</span>: 操作单向链表
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 15, 2019 8:54:46 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SinglyLinkedList</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

	SinglyListNode&lt;T&gt; headNode;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">createLinkedList</span><span class="hljs-params">()</span> </span>&#123;
		headNode = <span class="hljs-keyword">new</span> SinglyListNode&lt;T&gt;();
		<span class="hljs-comment">// headNode.setData(0);// attention: the header node is zero default</span>
	&#125;

	<span class="hljs-comment">// get the header node of the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">getHeaderNode</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> headNode.getData();
	&#125;

	<span class="hljs-comment">// get the length of the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getListLength</span><span class="hljs-params">(<span class="hljs-comment">/* ListNode headNode */</span>)</span> </span>&#123;
		<span class="hljs-keyword">int</span> length = <span class="hljs-number">0</span>;
		SinglyListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
			currentNode = currentNode.getNext();
			length++;
		&#125;
		<span class="hljs-keyword">return</span> length;
	&#125;

	<span class="hljs-comment">// add a new node into the linked list by specified position</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> SinglyListNode&lt;T&gt; <span class="hljs-title">insertInLinked</span><span class="hljs-params">(SinglyListNode&lt;T&gt; nodeToInsert, <span class="hljs-keyword">int</span> position)</span> </span>&#123;

		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the linked list is empty !"</span>);
			<span class="hljs-keyword">return</span> nodeToInsert;
		&#125;
		<span class="hljs-keyword">int</span> size = getListLength();
		<span class="hljs-keyword">if</span> (position &gt; size + <span class="hljs-number">1</span> || position &lt; <span class="hljs-number">1</span>) &#123;
			System.err.println(<span class="hljs-string">"Position of node to insert is invalid. The vaild inputs are 1 to "</span> + (size + <span class="hljs-number">1</span>));
			<span class="hljs-keyword">return</span> headNode;
		&#125;
		<span class="hljs-keyword">if</span> (position == <span class="hljs-number">1</span>) &#123;
			nodeToInsert.setNext(headNode);
			headNode = nodeToInsert;
			<span class="hljs-keyword">return</span> nodeToInsert;
		&#125; <span class="hljs-keyword">else</span> &#123;

			<span class="hljs-keyword">int</span> count = <span class="hljs-number">1</span>;
			SinglyListNode&lt;T&gt; previousNode = headNode;
			<span class="hljs-keyword">while</span> (count &lt; position - <span class="hljs-number">1</span>) &#123;
				previousNode = previousNode.getNext();<span class="hljs-comment">// 待插节点的前节点</span>
				count++;
			&#125;

			SinglyListNode&lt;T&gt; currentNode = previousNode.getNext();<span class="hljs-comment">// 待插节点的后节点</span>
			nodeToInsert.setNext(currentNode);
			previousNode.setNext(nodeToInsert);
		&#125;

		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// delete the node by the specified position in the linked node</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">deleteNodeFromLinkedList</span><span class="hljs-params">(<span class="hljs-comment">/* ListNode headNode, */</span> <span class="hljs-keyword">int</span> position)</span> </span>&#123;
		<span class="hljs-keyword">int</span> size = getListLength();
		<span class="hljs-keyword">if</span> (position &gt; size || position &lt; <span class="hljs-number">1</span>) &#123;
			System.err.println(<span class="hljs-string">"Position of node to insert is invalid. The vaild inputs are 1 to"</span> + (size + <span class="hljs-number">1</span>));
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;
		<span class="hljs-keyword">if</span> (position == <span class="hljs-number">1</span>) &#123;
			SinglyListNode&lt;T&gt; currentNode = headNode.getNext();
			headNode = currentNode;
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
		&#125; <span class="hljs-keyword">else</span> &#123;<span class="hljs-comment">// 删除中间或表尾结点</span>
			<span class="hljs-keyword">int</span> count = <span class="hljs-number">1</span>;
			SinglyListNode&lt;T&gt; previousNode = headNode.getNext();
			<span class="hljs-keyword">while</span> (count &lt; position) &#123;
				previousNode = previousNode.getNext(); <span class="hljs-comment">// 找到待删节点的前节点</span>
				count++;
			&#125;

			SinglyListNode&lt;T&gt; currentNode = previousNode.getNext();<span class="hljs-comment">// 待删节点</span>
			previousNode.setNext(currentNode.getNext());
			currentNode = <span class="hljs-keyword">null</span>;
		&#125;
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// delete the singly linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">destroyLinkedList</span><span class="hljs-params">(<span class="hljs-comment">/* ListNode headNode */</span>)</span> </span>&#123;

		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the singly linked list is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;
		System.out.print(<span class="hljs-string">"delete the node: "</span>);
		<span class="hljs-keyword">while</span> (headNode != <span class="hljs-keyword">null</span>) &#123;
			System.out.print(headNode.getData() + <span class="hljs-string">" , "</span>);
			headNode = headNode.getNext();
		&#125;
		System.out.println();
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// Iterate through all the data in the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">traverseNode</span><span class="hljs-params">( <span class="hljs-comment">/* ListNode headNode */</span>)</span> </span>&#123;

		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the linked node is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;
		SinglyListNode&lt;T&gt; currentNode = headNode;
		System.out.print(<span class="hljs-string">"All of node: "</span>);
		<span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
			System.out.print(currentNode.getData() + <span class="hljs-string">" , "</span>);
			currentNode = currentNode.getNext();
		&#125;
		System.out.println();
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;

		SinglyLinkedList&lt;String&gt; list = <span class="hljs-keyword">new</span> SinglyLinkedList&lt;String&gt;();

		<span class="hljs-comment">// 定义待插入链表的节点</span>
		SinglyListNode&lt;String&gt; a = <span class="hljs-keyword">new</span> SinglyListNode&lt;String&gt;();
		a.setData(<span class="hljs-string">"A"</span>);
		SinglyListNode&lt;String&gt; b = <span class="hljs-keyword">new</span> SinglyListNode&lt;String&gt;();
		b.setData(<span class="hljs-string">"B"</span>);
		SinglyListNode&lt;String&gt; c = <span class="hljs-keyword">new</span> SinglyListNode&lt;String&gt;();
		c.setData(<span class="hljs-string">"C"</span>);

		<span class="hljs-comment">// 向单向链表中添加新的节点</span>
		list.createLinkedList();
		list.insertInLinked(a, <span class="hljs-number">1</span>);
		list.insertInLinked(b, <span class="hljs-number">2</span>);
		list.insertInLinked(c, <span class="hljs-number">1</span>);

		System.out.println(<span class="hljs-string">"The size of linked list: "</span> + list.getListLength());
		System.out.println(<span class="hljs-string">"The header node : "</span> + list.getHeaderNode());
		list.traverseNode();
		System.out.println(<span class="hljs-string">"Delete the node which the position is first: "</span> + list.deleteNodeFromLinkedList(<span class="hljs-number">1</span>));
		list.traverseNode();
		System.out.println(<span class="hljs-string">"Delete all of node: "</span> + list.destroyLinkedList());
		System.out.println(<span class="hljs-string">"The size of linked list: "</span> + list.getListLength());
		list.traverseNode();

	&#125;
&#125;</code></pre></div></li>
<li><em>程序运行结果</em><div class="hljs"><pre><code class="hljs java">The size of linked list: <span class="hljs-number">4</span>
The header node : C
All of node: C , A , B , <span class="hljs-keyword">null</span> , 
Delete the node which the position is first: <span class="hljs-keyword">true</span>
All of node: A , B , <span class="hljs-keyword">null</span> , 
delete the node: A , B , <span class="hljs-keyword">null</span> , 
Delete all of node: <span class="hljs-keyword">true</span>
The size of linked list: <span class="hljs-number">0</span>
Error: the linked node is empty !</code></pre></div>

</li>
</ol>
<h4 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h4><ol>
<li><p><em>定义链表</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.linkedlist;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: BidirectionalLinkList
 * <span class="hljs-doctag">@Description</span>: 双向链表
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 16, 2019 2:31:09 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DoubleListNode</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;

	<span class="hljs-keyword">private</span> E data;
	<span class="hljs-keyword">private</span> DoubleListNode&lt;E&gt; next;<span class="hljs-comment">// the pointer</span>
	<span class="hljs-keyword">private</span> DoubleListNode&lt;E&gt; previous;

	<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">getData</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> data;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setData</span><span class="hljs-params">(E data)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.data = data;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> DoubleListNode&lt;E&gt; <span class="hljs-title">getNext</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> next;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setNext</span><span class="hljs-params">(DoubleListNode&lt;E&gt; next)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.next = next;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> DoubleListNode&lt;E&gt; <span class="hljs-title">getPrevious</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> previous;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setPrevious</span><span class="hljs-params">(DoubleListNode&lt;E&gt; previous)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.previous = previous;
	&#125;
&#125;</code></pre></div></li>
<li><p><em>操作双向链表的示例程序</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.linkedlist;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: CircularList
 * <span class="hljs-doctag">@Description</span>: 操作循环链表
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@date</span>: Apr 16, 2019 2:28:27 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DoubleLinkedList</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

	DoubleListNode&lt;T&gt; headNode;

	<span class="hljs-comment">// initialize the circular list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">createCircularList</span><span class="hljs-params">()</span> </span>&#123;
		headNode = <span class="hljs-keyword">new</span> DoubleListNode&lt;T&gt;();<span class="hljs-comment">// Attention: the header node is empty default</span>
		<span class="hljs-comment">// headNode.setData(0);</span>
	&#125;

	<span class="hljs-comment">// get the length of the circular list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getLength</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">int</span> length = <span class="hljs-number">0</span>;
		DoubleListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
			currentNode = currentNode.getNext();
			length++;
		&#125;

		<span class="hljs-keyword">return</span> length;
	&#125;

	<span class="hljs-comment">// get the header node of the double linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> T <span class="hljs-title">getHeaderNode</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the double linked list is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
		&#125;
		<span class="hljs-keyword">return</span> headNode.getData();
	&#125;

	<span class="hljs-comment">// add new node into the double linked list by the specified position</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> DoubleListNode&lt;T&gt; <span class="hljs-title">insertNode</span><span class="hljs-params">(DoubleListNode&lt;T&gt; newNode, <span class="hljs-keyword">int</span> position)</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the double linked list is empty !"</span>);
		&#125;
		<span class="hljs-keyword">int</span> size = getLength();
		<span class="hljs-keyword">if</span> (position &lt; <span class="hljs-number">1</span> || position &gt; size + <span class="hljs-number">1</span>) &#123;
			System.err.println(<span class="hljs-string">"Position of node to insert is invalid. The vaild inputs are 1 to "</span> + (size + <span class="hljs-number">1</span>));
			<span class="hljs-keyword">return</span> headNode;
		&#125;

		<span class="hljs-keyword">if</span> (position == <span class="hljs-number">1</span>) &#123;
			newNode.setNext(headNode);
			headNode.setPrevious(newNode);
			headNode = newNode;<span class="hljs-comment">// 更新头结点</span>
			<span class="hljs-keyword">return</span> headNode;
		&#125; <span class="hljs-keyword">else</span> &#123;
			<span class="hljs-keyword">int</span> count = <span class="hljs-number">1</span>;
			DoubleListNode&lt;T&gt; previousNode = headNode;
			<span class="hljs-keyword">while</span> (count &lt; position - <span class="hljs-number">1</span>) &#123;
				previousNode = previousNode.getNext();
				count++;
			&#125;
			DoubleListNode&lt;T&gt; currentNode = previousNode.getNext();<span class="hljs-comment">// 找到待插位置的节点</span>
			newNode.setNext(currentNode);
			<span class="hljs-keyword">if</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;<span class="hljs-comment">// 如果待插位置的节点不是尾节点</span>
				currentNode.setPrevious(newNode);
			&#125;
			previousNode.setNext(newNode);
			newNode.setPrevious(previousNode);
		&#125;
		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// delete node by the spcified position in the double linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">deleteNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> position)</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the circular list is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
		&#125;

		<span class="hljs-keyword">if</span> (position == <span class="hljs-number">1</span>) &#123;
			DoubleListNode&lt;T&gt; secondNode = headNode.getNext();
			secondNode.setPrevious(<span class="hljs-keyword">null</span>);
			headNode = secondNode;<span class="hljs-comment">// as the header node</span>
		&#125; <span class="hljs-keyword">else</span> &#123;
			<span class="hljs-keyword">int</span> count = <span class="hljs-number">1</span>;
			<span class="hljs-comment">//// `previousNode`与`headNode`操作的是同一个对象哟 ! ////</span>
			DoubleListNode&lt;T&gt; previousNode = headNode;
			<span class="hljs-keyword">while</span> (count &lt; position - <span class="hljs-number">1</span>) &#123;
				previousNode = previousNode.getNext();<span class="hljs-comment">// 待删节点的前节点</span>
				count++;
			&#125;

			DoubleListNode&lt;T&gt; currentNode = previousNode.getNext();<span class="hljs-comment">// 待删节点</span>
			DoubleListNode&lt;T&gt; laterNode = currentNode.getNext();<span class="hljs-comment">// 待删节点的后节点</span>

			previousNode.setNext(laterNode);
			<span class="hljs-keyword">if</span> (laterNode != <span class="hljs-keyword">null</span>) &#123;
				laterNode.setPrevious(previousNode);
				currentNode = <span class="hljs-keyword">null</span>;
			&#125;
		&#125;
		<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
	&#125;

	<span class="hljs-comment">// Iterate through all the data in the linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverseNode</span><span class="hljs-params">()</span> </span>&#123;
		DoubleListNode&lt;T&gt; node = headNode;
		<span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the circular list is empty !"</span>);
		&#125;
		<span class="hljs-keyword">while</span> (node != <span class="hljs-keyword">null</span>) &#123;
			System.out.println(<span class="hljs-string">"the node: "</span> + node.getData());
			node = node.getNext();
		&#125;
	&#125;

	<span class="hljs-comment">// destroy the double linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">destroyList</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.out.println(<span class="hljs-string">"Error: the circular list is empty !"</span>);
		&#125;
		<span class="hljs-keyword">while</span> (headNode != <span class="hljs-keyword">null</span>) &#123;
			System.out.println(<span class="hljs-string">"delete the node: "</span> + headNode.getData());
			headNode = headNode.getNext();
		&#125;
	&#125;

	<span class="hljs-comment">// Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;

		<span class="hljs-comment">// CircularList&lt;Integer&gt; list = new CircularList&lt;Integer&gt;();</span>
		DoubleLinkedList&lt;Character&gt; list = <span class="hljs-keyword">new</span> DoubleLinkedList&lt;Character&gt;();

		<span class="hljs-comment">// 初始化待插节点</span>
		DoubleListNode&lt;Character&gt; a = <span class="hljs-keyword">new</span> DoubleListNode&lt;Character&gt;();
		a.setData(<span class="hljs-string">'a'</span>);
		DoubleListNode&lt;Character&gt; b = <span class="hljs-keyword">new</span> DoubleListNode&lt;Character&gt;();
		b.setData(<span class="hljs-string">'b'</span>);
		DoubleListNode&lt;Character&gt; c = <span class="hljs-keyword">new</span> DoubleListNode&lt;Character&gt;();
		c.setData(<span class="hljs-string">'c'</span>);

		<span class="hljs-comment">// 向双向链表中添加新节点</span>
		list.createCircularList();
		list.insertNode(a, <span class="hljs-number">1</span>);
		list.insertNode(b, <span class="hljs-number">2</span>);
		list.insertNode(c, <span class="hljs-number">3</span>);

		System.out.println(<span class="hljs-string">"-------- traverse --------"</span>);
		list.traverseNode();
		System.out.println(<span class="hljs-string">"--------------------------"</span>);
		System.out.println(<span class="hljs-string">"The header node: "</span> + list.getHeaderNode());
		System.out.println(<span class="hljs-string">"The length of the circular list: "</span> + list.getLength());
		System.out.println(<span class="hljs-string">"Delete the node which the position is one: "</span> + list.deleteNode(<span class="hljs-number">1</span>));
		System.out.println(<span class="hljs-string">"-------- traverse --------"</span>);
		list.traverseNode();
		System.out.println(<span class="hljs-string">"--------------------------"</span>);
		System.out.println(<span class="hljs-string">"The header node: "</span> + list.getHeaderNode());
		System.out.println(<span class="hljs-string">"The length of the circular list: "</span> + list.getLength());

		System.out.println();
		list.destroyList();
		System.out.println(<span class="hljs-string">"The header node: "</span> + list.getHeaderNode());
	&#125;
&#125;</code></pre></div>
</li>
<li><p><em>程序运行结果</em></p>
<div class="hljs"><pre><code class="hljs java">-------- traverse --------
the node: a
the node: b
the node: c
the node: null
--------------------------
The header node: a
The length of the circular list: 4
Delete the node which the position is one: true
-------- traverse --------
the node: b
the node: c
the node: null
--------------------------
The header node: b
The length of the circular list: 3

delete the node: b
delete the node: c
delete the node: null
The header node: null
Error: the double linked list is empty !
``` 

#### 循环链表
1. *定义一个链表*
```java
package pers.huangyuhui.linkedlist;

/**
 * @ClassName: CircularListNode
 * @Description: 循环链表
 * @author: HuangYuhui
 * @date: Apr 17, 2019 9:52:23 AM
 * 
 */
public class ListNode&lt;T&gt; &#123;

	private T data;
	private ListNode&lt;T&gt; next;

	public T getData() &#123;
		return data;
	&#125;

	public void setData(T data) &#123;
		this.data = data;
	&#125;

	public ListNode&lt;T&gt; getNext() &#123;
		return next;
	&#125;

	public void setNext(ListNode&lt;T&gt; next) &#123;
		this.next = next;
	&#125;

&#125;</code></pre></div>
</li>
<li><p><em>操作循环链表的示例程序</em></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.linkedlist;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@ClassName</span>: CircularLinkedList
 * <span class="hljs-doctag">@Description</span>: 操作循环链表
 * <span class="hljs-doctag">@author</span>: HuangYuhui
 * <span class="hljs-doctag">@param</span> &lt;T&gt;
 * <span class="hljs-doctag">@date</span>: Apr 16, 2019 7:25:36 PM
 * 
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">CircularLinkedList</span>&lt;<span class="hljs-title">T</span>&gt; </span>&#123;

	<span class="hljs-comment">// get the length of the circular linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getLength</span><span class="hljs-params">(ListNode&lt;T&gt; headNode)</span> </span>&#123;
		<span class="hljs-keyword">int</span> length = <span class="hljs-number">0</span>;
		ListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
			currentNode = currentNode.getNext();
			length++;
			<span class="hljs-keyword">if</span> (currentNode == headNode) &#123;
				<span class="hljs-keyword">break</span>;
			&#125;
		&#125;
		<span class="hljs-keyword">return</span> length;
	&#125;

	<span class="hljs-comment">// traverse the node of the circular linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverseNode</span><span class="hljs-params">(ListNode&lt;T&gt; headNode)</span> </span>&#123;
		ListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
			System.out.print(currentNode.getData() + <span class="hljs-string">" -&gt; "</span>);
			currentNode = currentNode.getNext();
			<span class="hljs-keyword">if</span> (currentNode == headNode) &#123;
				<span class="hljs-keyword">break</span>;
			&#125;
		&#125;
		System.out.print(<span class="hljs-string">"headNode("</span> + currentNode.getData() + <span class="hljs-string">")\n"</span>);
	&#125;

	<span class="hljs-comment">// add new node at the tail of linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insertAtListTail</span><span class="hljs-params">(ListNode&lt;T&gt; headNode, ListNode&lt;T&gt; newNode)</span> </span>&#123;

		ListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">while</span> (currentNode.getNext() != headNode) &#123;
			<span class="hljs-comment">//// 注意: 由于`currentNode`无变化,导致`currentNode.getNext() != headNode`继而进入进入死循环 !////</span>
			<span class="hljs-comment">// currentNode.setNext(currentNode.getNext());</span>
			currentNode = currentNode.getNext();
		&#125;
		newNode.setNext(newNode);
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			headNode = newNode;
		&#125; <span class="hljs-keyword">else</span> &#123;
			newNode.setNext(headNode);
			currentNode.setNext(newNode);
		&#125;
	&#125;

	<span class="hljs-comment">// add new node at the header of linked list</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> ListNode&lt;T&gt; <span class="hljs-title">insertAtListHeader</span><span class="hljs-params">(ListNode&lt;T&gt; headNode, ListNode&lt;T&gt; newNode)</span> </span>&#123;

		ListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">while</span> (currentNode.getNext() != headNode) &#123;
			currentNode = currentNode.getNext();<span class="hljs-comment">// 尾节点</span>
		&#125;
		newNode.setNext(newNode);<span class="hljs-comment">// 指针指向自身</span>
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			headNode = newNode;
		&#125;
		newNode.setNext(headNode);
		currentNode.setNext(newNode);
		<span class="hljs-comment">// 注意: 此时链表头结点已更新! 所以应该返回更新后的头节点继而避免遍历时出现死循环!!!</span>
		headNode = newNode;
		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// add the new node by the specified index</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> ListNode&lt;T&gt; <span class="hljs-title">insertNodeByIndex</span><span class="hljs-params">(ListNode&lt;T&gt; headNode, ListNode&lt;T&gt; newNode, <span class="hljs-keyword">int</span> position)</span> </span>&#123;

		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.out.println(<span class="hljs-string">"Error: the circular list is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
		&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (position == <span class="hljs-number">1</span>) &#123;
			insertAtListHeader(headNode, newNode);
		&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (position == getLength(headNode)) &#123;
			insertAtListTail(headNode, newNode);
		&#125; <span class="hljs-keyword">else</span> &#123;
			ListNode&lt;T&gt; currentNode = headNode;
			ListNode&lt;T&gt; temp = headNode;
			<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; position - <span class="hljs-number">1</span>; i++) &#123;
				temp = currentNode;<span class="hljs-comment">// 待插节点的前节点</span>
				currentNode = currentNode.getNext();<span class="hljs-comment">// 待插节点</span>
			&#125;
			temp.setNext(newNode);
			newNode.setNext(currentNode);
		&#125;
		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// delete the last node</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">deleteLastNode</span><span class="hljs-params">(ListNode&lt;T&gt; headNode)</span> </span>&#123;

		ListNode&lt;T&gt; temp = headNode;
		ListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the circular list is empty !"</span>);
		&#125;
		<span class="hljs-keyword">while</span> (currentNode.getNext() != headNode) &#123;
			temp = currentNode; <span class="hljs-comment">// 尾节点的前一个节点</span>
			currentNode = currentNode.getNext();
		&#125;
		temp.setNext(headNode);
		currentNode = <span class="hljs-keyword">null</span>;
	&#125;

	<span class="hljs-comment">// delete the header node</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> ListNode&lt;T&gt; <span class="hljs-title">deleteHeaderNode</span><span class="hljs-params">(ListNode&lt;T&gt; headNode)</span> </span>&#123;
		ListNode&lt;T&gt; currentNode = headNode;
		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.err.println(<span class="hljs-string">"Error: the circular list is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
		&#125;

		<span class="hljs-keyword">while</span> (currentNode.getNext() != headNode) &#123;
			<span class="hljs-comment">// currentNode.setNext(currentNode.getNext());//死循环</span>
			currentNode = currentNode.getNext();
		&#125;
		currentNode.setNext(headNode.getNext());
		<span class="hljs-comment">// 注意: 此时链表头结点已更新! 所以应该返回更新后的头节点继而避免遍历时出现死循环!!!</span>
		headNode = headNode.getNext();
		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// delete the node by the specified index</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> ListNode&lt;T&gt; <span class="hljs-title">deleteNodeByIndex</span><span class="hljs-params">(ListNode&lt;T&gt; headNode, <span class="hljs-keyword">int</span> position)</span> </span>&#123;

		<span class="hljs-keyword">if</span> (headNode == <span class="hljs-keyword">null</span>) &#123;
			System.out.println(<span class="hljs-string">"Error: the circular linked list is empty !"</span>);
			<span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
		&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (position == <span class="hljs-number">1</span>) &#123;
			deleteHeaderNode(headNode);
		&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (position == getLength(headNode)) &#123;
			deleteLastNode(headNode);
		&#125; <span class="hljs-keyword">else</span> &#123;
			ListNode&lt;T&gt; currentNode = headNode;
			ListNode&lt;T&gt; temp = headNode;
			<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; position - <span class="hljs-number">1</span>; i++) &#123;
				temp = currentNode;<span class="hljs-comment">// 待删节点的前节点</span>
				currentNode = currentNode.getNext();<span class="hljs-comment">// 待删节点</span>
			&#125;
			temp.setNext(currentNode.getNext());
		&#125;

		<span class="hljs-keyword">return</span> headNode;
	&#125;

	<span class="hljs-comment">// Test</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;

		<span class="hljs-comment">// 初始化链表头结点</span>
		CircularLinkedList&lt;Integer&gt; list = <span class="hljs-keyword">new</span> CircularLinkedList&lt;&gt;();
		ListNode&lt;Integer&gt; headNode = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		headNode.setData(<span class="hljs-number">1</span>);<span class="hljs-comment">// 初始化链表头结点</span>
		headNode.setNext(headNode);<span class="hljs-comment">// 节点指针指向自身</span>

		<span class="hljs-comment">// 初始化待插入的链表节点</span>
		ListNode&lt;Integer&gt; a = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		a.setData(<span class="hljs-number">2</span>);
		ListNode&lt;Integer&gt; b = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		b.setData(<span class="hljs-number">3</span>);
		ListNode&lt;Integer&gt; c = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		c.setData(<span class="hljs-number">4</span>);
		ListNode&lt;Integer&gt; d = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		d.setData(<span class="hljs-number">100</span>);
		ListNode&lt;Integer&gt; e = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		e.setData(<span class="hljs-number">101</span>);
		ListNode&lt;Integer&gt; f = <span class="hljs-keyword">new</span> ListNode&lt;&gt;();
		f.setData(<span class="hljs-number">0</span>);

		<span class="hljs-comment">// 向链表的尾部添加三个节点</span>
		System.out.print(<span class="hljs-string">"the origin node: "</span>);
		list.insertAtListTail(headNode, a);
		list.insertAtListTail(headNode, b);
		list.insertAtListTail(headNode, c);
		list.traverseNode(headNode);
		System.out.println(<span class="hljs-string">"the length of the list: "</span> + list.getLength(headNode));

		<span class="hljs-comment">// 向链表中添加两个头结点</span>
		System.out.print(<span class="hljs-string">"add two header node: "</span>);
		ListNode&lt;Integer&gt; newHeadNode = list.insertAtListHeader(headNode, d);
		<span class="hljs-comment">// 注意: 由于`头结点`已在`insertAtListHeader`中已更新所以要向`traverseNode`传入新的头结点</span>
		ListNode&lt;Integer&gt; newHeadNode2 = list.insertAtListHeader(newHeadNode, e);
		list.traverseNode(newHeadNode2);
		System.out.println(<span class="hljs-string">"the length of the list: "</span> + list.getLength(headNode));

		<span class="hljs-comment">// 在链表的指定位置上插入新的节点</span>
		System.out.print(<span class="hljs-string">"Insert the new node at position 3: "</span>);
		list.insertNodeByIndex(headNode, f, <span class="hljs-number">3</span>);
		list.traverseNode(newHeadNode2);
		System.out.println(<span class="hljs-string">"the length of the list: "</span> + list.getLength(headNode));

		<span class="hljs-comment">// 删除链表的尾节点</span>
		System.out.print(<span class="hljs-string">"delete the tail node:  "</span>);
		list.deleteLastNode(newHeadNode2);
		list.traverseNode(newHeadNode2);
		System.out.println(<span class="hljs-string">"the length of the list: "</span> + list.getLength(headNode));

		<span class="hljs-comment">// 注意: 由于`头结点`已在`deleteHeaderNode`中已更新所以要向`traverseNode`传入新的头结点</span>
		ListNode&lt;Integer&gt; newHeadNode3 = list.deleteHeaderNode(newHeadNode2);
		System.out.print(<span class="hljs-string">"delete the header node:  "</span>);
		list.traverseNode(newHeadNode3);
		System.out.println(<span class="hljs-string">"the length of the list: "</span> + list.getLength(headNode));

		<span class="hljs-comment">// 删除链表中指定位置的节点</span>
		ListNode&lt;Integer&gt; newHeadNode4 = list.deleteNodeByIndex(newHeadNode3, <span class="hljs-number">4</span>);
		System.out.print(<span class="hljs-string">"delete the fourth node: "</span>);
		list.traverseNode(newHeadNode4);
		System.out.println(<span class="hljs-string">"the length of the list: "</span> + list.getLength(headNode));
	&#125;
&#125;</code></pre></div>
</li>
<li><p><em>程序运行结果</em></p>
<div class="hljs"><pre><code class="hljs java">the origin node: <span class="hljs-number">1</span> -&gt; <span class="hljs-number">2</span> -&gt; <span class="hljs-number">3</span> -&gt; <span class="hljs-number">4</span> -&gt; headNode(<span class="hljs-number">1</span>)
the length of the list: <span class="hljs-number">4</span>
add two header node: <span class="hljs-number">101</span> -&gt; <span class="hljs-number">100</span> -&gt; <span class="hljs-number">1</span> -&gt; <span class="hljs-number">2</span> -&gt; <span class="hljs-number">3</span> -&gt; <span class="hljs-number">4</span> -&gt; headNode(<span class="hljs-number">101</span>)
the length of the list: <span class="hljs-number">6</span>
Insert the <span class="hljs-keyword">new</span> node at position <span class="hljs-number">3</span>: <span class="hljs-number">101</span> -&gt; <span class="hljs-number">100</span> -&gt; <span class="hljs-number">1</span> -&gt; <span class="hljs-number">2</span> -&gt; <span class="hljs-number">0</span> -&gt; <span class="hljs-number">3</span> -&gt; <span class="hljs-number">4</span> -&gt; headNode(<span class="hljs-number">101</span>)
the length of the list: <span class="hljs-number">7</span>
delete the tail node:  <span class="hljs-number">101</span> -&gt; <span class="hljs-number">100</span> -&gt; <span class="hljs-number">1</span> -&gt; <span class="hljs-number">2</span> -&gt; <span class="hljs-number">0</span> -&gt; <span class="hljs-number">3</span> -&gt; headNode(<span class="hljs-number">101</span>)
the length of the list: <span class="hljs-number">6</span>
delete the header node:  <span class="hljs-number">100</span> -&gt; <span class="hljs-number">1</span> -&gt; <span class="hljs-number">2</span> -&gt; <span class="hljs-number">0</span> -&gt; <span class="hljs-number">3</span> -&gt; headNode(<span class="hljs-number">100</span>)
the length of the list: <span class="hljs-number">5</span>
delete the fourth node: <span class="hljs-number">100</span> -&gt; <span class="hljs-number">1</span> -&gt; <span class="hljs-number">2</span> -&gt; <span class="hljs-number">3</span> -&gt; headNode(<span class="hljs-number">100</span>)
the length of the list: <span class="hljs-number">4</span></code></pre></div>

</li>
</ol>
<h3 id="推荐书籍"><a href="#推荐书籍" class="headerlink" title="推荐书籍"></a>推荐书籍</h3><ul>
<li><em>上述示例程序主要参考本书籍：《数据结构与算法经典问题解析》—— 纳拉辛哈·卡路曼希[著]</em></li>
<li><em>很认真的说这是我大二至今看过的最好的一本关于数据结构与算法的书籍哟 ! 其针对不同问题提供多个具有不同复杂度的解决方案.兼顾自学教材和面试辅导的不同需求呢 !</em></li>
</ul>

            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/Java/">Java</a>
                    
                      <a class="hover-with-bg" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/2019/04/19/VOA-%E5%92%96%E5%95%A1%E5%88%B0%E5%BA%95%E5%A5%BD%E4%B8%8D%E5%A5%BD-%E7%A0%94%E7%A9%B6%E4%BA%BA%E5%91%98%E4%B9%9F%E8%AF%B4%E4%B8%8D%E6%B8%85/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">VOA:咖啡到底好不好?研究人员也说不清</span>
                        <span class="visible-mobile">Previous</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/2019/04/18/VOA-Google-s-Lookout-App-Helps-Blind-People-Experience-the-World/">
                        <span class="hidden-mobile">VOA:Google`s Lookout App Helps Blind People Experience the World</span>
                        <span class="visible-mobile">Next</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;TOC</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "详解Linked list的实现方式及其应用&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>







  
  
    <script>
      !function (e, t, a) {
        function r() {
          for (var e = 0; e < s.length; e++) s[e].alpha <= 0 ? (t.body.removeChild(s[e].el), s.splice(e, 1)) : (s[e].y--, s[e].scale += .004, s[e].alpha -= .013, s[e].el.style.cssText = "left:" + s[e].x + "px;top:" + s[e].y + "px;opacity:" + s[e].alpha + ";transform:scale(" + s[e].scale + "," + s[e].scale + ") rotate(45deg);background:" + s[e].color + ";z-index:99999");
          requestAnimationFrame(r)
        }

        function n() {
          var t = "function" == typeof e.onclick && e.onclick;
          e.onclick = function (e) {
            t && t(), o(e)
          }
        }

        function o(e) {
          var a = t.createElement("div");
          a.className = "heart", s.push({
            el: a,
            x: e.clientX - 5,
            y: e.clientY - 5,
            scale: 1,
            alpha: 1,
            color: c()
          }), t.body.appendChild(a)
        }

        function i(e) {
          var a = t.createElement("style");
          a.type = "text/css";
          try {
            a.appendChild(t.createTextNode(e))
          } catch (t) {
            a.styleSheet.cssText = e
          }
          t.getElementsByTagName("head")[0].appendChild(a)
        }

        function c() {
          return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
        }

        var s = [];
        e.requestAnimationFrame = e.requestAnimationFrame || e.webkitRequestAnimationFrame || e.mozRequestAnimationFrame || e.oRequestAnimationFrame || e.msRequestAnimationFrame || function (e) {
          setTimeout(e, 1e3 / 60)
        }, i(".heart{width: 10px;height: 10px;position: fixed;background: #f00;transform: rotate(45deg);-webkit-transform: rotate(45deg);-moz-transform: rotate(45deg);}.heart:after,.heart:before{content: '';width: inherit;height: inherit;background: inherit;border-radius: 50%;-webkit-border-radius: 50%;-moz-border-radius: 50%;position: fixed;}.heart:after{top: -5px;}.heart:before{left: -5px;}"), n(), r()
      }(window, document);
    </script>
  














</body>
</html>
